package demo3;
import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
public class Solution {
    //1.二叉搜索树的最小绝对差(dfs)
    /*public int prev;//上一个结点
    public int min;
    public int getMinimumDifference(TreeNode root) {
        this.prev = -1;
        this.min = Integer.MAX_VALUE;
        //中序遍历就是递增序列
        sort(root);
        return min;
    }
    private void sort(TreeNode root) {
        if(root == null) {
            return;
        }
        sort(root.left);
        if(prev == -1) {
            prev = root.val;
        }else {
            min = Math.min(Math.abs(prev - root.val), min);
            prev = root.val;
        }
        sort(root.right);
    }
    //2.N 叉树的前序遍历(dfs)
    public List<Integer> list = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        dfs(root);
        return list;
    }
    private void dfs(Node root) {
        if(root == null) {
            return;
        }
        list.add(root.val);
        for(int i = 0; i < root.children.size(); i++) {
            dfs(root.children.get(i));
        }
    }
    //3.二叉树的最大深度(另一种写法)
    public int maxDepth2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = maxDepth2(root.left);
        int right = maxDepth2(root.right);
        return Math.max(left, right) + 1;
    }
    //4.合并二叉树(dfs)
    //思路：将root2合并到root1上
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) {
            return null;
        }
        //若有一个为空，就返回那个不为空的结点
        if(root1 != null && root2 == null) {
            return root1;
        }
        if(root1 == null && root2 != null) {
            return root2;
        }
        //若都不为空，就加和到root1上
        if(root1 != null && root2 != null) {
            root1.val += root2.val;
        }
        //递归去加和左右子树
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }
    //4.合并二叉树(dfs)
    //思路：将root2合并到root1上
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) {
            return null;
        }
        if(root1 == null && root2 != null) {
            return root2;
        }
        if(root2 == null && root1 != null) {
            return root1;
        }
        TreeNode root = new TreeNode(root1.val + root2.val);
        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);
        return root;
    }
    //5.左叶子之和
    private int sum;
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null) {
            return 0;
        }
        //左子树不为空，并且左树的左树为空，左树的右树为空，保证了是左树的叶子结点
        if(root.left != null && root.left.left == null && root.left.right == null) {
            sum += root.left.val;
        }
        //递归的去看左右子树
        sumOfLeftLeaves(root.left);
        sumOfLeftLeaves(root.right);
        return sum;
    }

    //6.二叉树的所有路径(回溯剪枝)
  *//*  private List<String> ret = new ArrayList<>();
    private StringBuilder str = new StringBuilder();
    public List<String> binaryTreePaths(TreeNode root) {
        if(root == null) {
            return ret;
        }
        fundPaths(root);
        return ret;
    }
    private void fundPaths(TreeNode root) {
        if(root == null) {
            return;
        }
        //记录上一个str大小，方便剪枝条
        int size = str.length();
        //不为空就放入
        str.append(root.val);
        //确定是叶子结点,加入最后一个结点
        if(root.left == null && root.right == null) {
            ret.add(str.toString());
        }
        //不是叶子节点就继续(就算是也继续，后面会剪枝)
        str.append("->");
        //分别请递归左右子树
        fundPaths(root.left);
        fundPaths(root.right);
        //剪枝
        str.delete(size, str.length());
    }*//*

    //7.路径总和 II(回溯剪枝)
    private List<List<Integer>> ret = new LinkedList<>();
    private Deque<Integer> path = new LinkedList<>();//记录路径
    private int target;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        this.target = targetSum;
        int sum = 0;
        fundPath(root, sum);
        return ret;
    }
    private void fundPath(TreeNode root, int sum) {
        if(root == null) {
            return;
        }
        int sizePrev = path.size();//记录上一个长度(便于剪枝)
        int sumPrev = sum;//记录上一个和(便于剪枝)
        path.offerLast(root.val);
        sum += root.val;
        if(root.left == null && root.right == null && sum == target) {
            ret.add(new LinkedList<>(path));
        }
        //分别递归左右子树
        fundPath(root.left, sum);
        fundPath(root.right, sum);
        //剪枝
        path.pollLast();
        sum -= sumPrev;
    }

    //8.填充每个节点的下一个右侧节点指针(dfs简直太帅了！！！)
    public Node connect(Node root) {
        if(root == null) {
            return root;
        }
        dfs(root);
        return root;
    }
    private void dfs(Node root) {
        if(root == null) {
            return;
        }
        Node left = root.left;
        Node right = root.right;
        //直接串联下去
        while(left != null) {
            left.next = right;
            left = left.right;
            right = right.left;
        }
        dfs(root.left);
        dfs(root.right);
    }*/
    //9.二叉搜索树中第K小的元素
 /*   private List<Integer> list = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        //中序遍历得到顺序
        dfs(root);
        return list.get(k - 1);
    }
    private void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }
    //10.求根节点到叶节点数字之和(回溯剪枝)
    private List<String> list = new ArrayList<>();//保存每个路径的结点之和
    private StringBuilder path = new StringBuilder();//保存当前路径
    public int sumNumbers(TreeNode root) {
        //回溯剪枝
        dfs(root);
        //加和到一起
        int sum = 0;
        for(int i = 0; i < list.size(); i++) {
            sum += Integer.valueOf(list.get(i));
        }
        return sum;
    }
    private void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        path.append(root.val);
        //若左右子树都为空，说明此时是根节点
        if(root.left == null && root.right == null) {
            list.add(path.toString());
            //注意这里不能直接return，因为还要进行剪枝
        }
        //递归去看左右子树
        dfs(root.left);
        dfs(root.right);
        //这里也要剪枝，相当与左右子树走完回归的过程
        int now = path.length();
        path.deleteCharAt(now - 1);
    }*/

}
